#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;

// class Solution {
// public:
//     vector<int> maxSlidingWindow(vector<int>& nums, int k) {
//         vector<int> result;
//         priority_queue<int> Q;
//         for(int i = 0;i<nums.size();++i){
//             if(i<k){
//                 Q.push(nums[i]);
//                 Q.emplace(,)
//             }
//             else{
//                 result.push_back(maxQueue(Q));
//                 Q.pop();
//                 Q.push(nums[i]);
//             }
//         }
//         result.push_back(maxQueue(Q));
//         return result;
//     }
//     int maxQueue(queue<int> Q){
//         int maxValue = INT16_MIN;
//         while(!Q.empty()){
//             maxValue = max(Q.front(),maxValue);
//             Q.pop();
//         }
//         return maxValue;
//     }
// };

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int n = nums.size();
        deque<int> q;
        for (int i = 0; i < k; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
        }

        vector<int> ans = {nums[q.front()]};
        for (int i = k; i < n; ++i) {
            while (!q.empty() && nums[i] >= nums[q.back()]) {
                q.pop_back();
            }
            q.push_back(i);
            while (q.front() <= i - k) {
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};


int main(){
    Solution S;
    vector<int> nums = {1,3,-1,-3,5,3,6,7};
    vector<int> result = S.maxSlidingWindow(nums,3);
    for(int a:result){
        cout<<a<<endl;
    }
}